package com.huangpeng.algorithm.dataStructure;

/**
 * @Author huangpeng
 * @Title 莱文斯坦距离（Levenshtein distance）和最长公共子串长度（Longest common substring length）。其中，莱文斯坦距离允许增加、删除、替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作
 * @Package
 * @Date 2021/7/28 10:15
 * @Description
 * @Version 1.0
 */
public class LevenshteinDistance {
    private char[] a = "mitcmu".toCharArray();//字符串a
    private char[] b = "mtacnu".toCharArray();//字符串b
    private int n = a.length;//a字符串的长度
    private int m = b.length;//b字符串的长度
    private int minDist = Integer.MAX_VALUE;// 存储结果

    /**
     * 计算最短编辑距离
     * 调用方式 lwstBT(0, 0, 0);
     * @param i
     * @param j
     * @param edist
     * @return
     */
    public Integer lwstBT(int i, int j, int edist){
        if(i == n || j == m){
            if(i < n){
                edist += (n - i);
            }
            if(j < m){
                edist += (m - j);
            }
            if(edist < minDist){
                minDist = edist;
            }
            return minDist;
        }
        if(a[i] == b[j]){// 两个字符匹配
            lwstBT(i + 1,j + 1,edist);//递归
        }else{// 两个字符不匹配
            lwstBT(i + 1, j, edist + 1); // 删除 a[i] 或者 b[j] 前添加一个字符
            lwstBT(i, j + 1, edist + 1); // 删除 b[j] 或者 a[i] 前添加一个字符
            lwstBT(i + 1, j + 1, edist + 1); // 将 a[i] 和 b[j] 替换为相同字符
        }
        return minDist;
    }

    /**
     * 计算最长公共子串长度
     * 状态转移方程写出来，就是下面这个样子：
     * 如果：a[i]==b[j]，那么：max_lcs(i, j) 就等于：
     * max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))；
     * 如果：a[i]!=b[j]，那么：max_lcs(i, j) 就等于：
     * max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))；
     * 其中 max 表示求三数中的最大值。
     * @param a
     * @param n
     * @param b
     * @param m
     * @return
     */
    public int lcs(char[] a, int n, char[] b, int m) {
        int[][] maxlcs = new int[n][m];
        for (int i = 0; i < m; i++) {// 初始化第 0 行：a[0..0] 与 b[0..j] 的 maxlcs
            if(a[0] == b[i]){
                maxlcs[0][i] = 1;
            }else if(i != 0){
                maxlcs[0][i] = maxlcs[0][i - 1];
            }else{
                maxlcs[0][i] = 0;
            }
        }
        for (int i = 0; i < n; i++) {// 初始化第 0 列：a[0..i] 与 b[0..0] 的 maxlcs
            if(a[i] == b[0]){
                maxlcs[i][0] = 1;
            }else if(i != 0){
                maxlcs[i][0] = maxlcs[i - 1][0];
            }else{
                maxlcs[i][0] = 0;
            }
        }
        for (int i = 1; i < n; i++) {// 填表
            for (int j = 1; j < m; j++) {
                if(a[i] == b[j]){
                    maxlcs[i][j] = getMax(maxlcs[i][j - 1],maxlcs[i - 1][j],maxlcs[i - 1][j - 1] + 1);
                }else{
                    maxlcs[i][j] = getMax(maxlcs[i][j - 1],maxlcs[i - 1][j],maxlcs[i - 1][j - 1]);
                }
            }
        }
        return maxlcs[n - 1][m - 1];
    }

    private int getMax(int x, int y, int z) {
        int maxv = Integer.MIN_VALUE;
        if(x > maxv){
            maxv = x;
        }
        if(y > maxv){
            maxv = y;
        }
        if(z > maxv){
            maxv = z;
        }

        return maxv;
    }

    public static void main(String[] args) {
        LevenshteinDistance l = new LevenshteinDistance();
        Integer mindist = l.lwstBT(0,0,0);
        System.out.println("************* " + mindist);

        int maxlcs = l.lcs(l.a,l.n,l.b,l.m);
        System.out.println("************* " + maxlcs);
    }
}
